#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
using namespace std;

struct Job {
    string name;
    int arrive;
    int run;
    int start = -1;
    int finish = -1;
    int turnaround = 0;
    double weighted_turnaround = 0.0;
    bool done = false;
    int remain = 0; // 剩余运行时间
};

void print_order(const vector<string>& order, const string& algo) {
    cout << "[" << algo << "] 调度顺序: ";
    for (size_t i = 0; i < order.size(); ++i) {
        cout << order[i];
        if (i != order.size() - 1) cout << " -> ";
    }
    cout << endl;
}

void print_result(const vector<Job>& jobs, const string& algo) {
    double sum_turn = 0, sum_weighted = 0;
    cout << "\n[" << algo << "] 调度结果：\n";
    cout << "作业\t到达\t运行\t开始\t完成\t周转\t带权周转\n";
    for (const auto& job : jobs) {
        cout << job.name << "\t" << job.arrive << "\t" << job.run << "\t"
             << job.start << "\t" << job.finish << "\t"
             << job.turnaround << "\t" << fixed << setprecision(2)
             << job.weighted_turnaround << "\n";
        sum_turn += job.turnaround;
        sum_weighted += job.weighted_turnaround;
    }
    cout << "平均周转时间: " << sum_turn / jobs.size()
         << "，平均带权周转时间: " << sum_weighted / jobs.size() << "\n";
}

// 先来先服务
void schedule_FCFS(vector<Job> jobs) {
    vector<Job> waitQ = jobs;
    vector<Job> runningQ;
    vector<Job> finishQ;
    vector<string> order;
    int time = 0;

    sort(waitQ.begin(), waitQ.end(), [](const Job& a, const Job& b) {
        return a.arrive < b.arrive;
    });

    while (finishQ.size() < jobs.size()) {
        // 检查运行队列，移除已完成作业
        for (auto it = runningQ.begin(); it != runningQ.end();) {
            if (it->remain == 0) {
                Job finished = *it;
                finished.finish = time;
                finished.turnaround = finished.finish - finished.arrive;
                finished.weighted_turnaround = (double)finished.turnaround / finished.run;
                finishQ.push_back(finished);
                it = runningQ.erase(it);
            } else {
                ++it;
            }
        }
        // 运行队列补充（FCFS：按到达顺序）
        for (auto it = waitQ.begin(); it != waitQ.end();) {
            if (it->arrive <= time && runningQ.size() < 2) {
                Job job = *it;
                job.start = time;
                job.remain = job.run;
                runningQ.push_back(job);
                order.push_back(job.name);
                it = waitQ.erase(it);
            } else {
                ++it;
            }
        }
        // 运行队列作业运行1秒
        for (auto& job : runningQ) {
            if (job.remain > 0) job.remain--;
        }
        time++;
    }
    sort(finishQ.begin(), finishQ.end(), [](const Job& a, const Job& b) {
        return a.name < b.name;
    });
    print_order(order, "先来先服务 FCFS");
    print_result(finishQ, "先来先服务 FCFS");
}

// 短作业优先
void schedule_SJF(vector<Job> jobs) {
    vector<Job> waitQ = jobs;
    vector<Job> runningQ;
    vector<Job> finishQ;
    vector<string> order;
    int time = 0;

    while (finishQ.size() < jobs.size()) {
        // 检查运行队列，移除已完成作业
        for (auto it = runningQ.begin(); it != runningQ.end();) {
            if (it->remain == 0) {
                Job finished = *it;
                finished.finish = time;
                finished.turnaround = finished.finish - finished.arrive;
                finished.weighted_turnaround = (double)finished.turnaround / finished.run;
                finishQ.push_back(finished);
                it = runningQ.erase(it);
            } else {
                ++it;
            }
        }
        // 运行队列补充（SJF：从已到达作业中选最短的）
        while (runningQ.size() < 2) {
            int idx = -1, min_run = 1e9;
            for (int i = 0; i < waitQ.size(); ++i) {
                if (waitQ[i].arrive <= time && waitQ[i].run < min_run) {
                    min_run = waitQ[i].run;
                    idx = i;
                }
            }
            if (idx != -1) {
                Job job = waitQ[idx];
                job.start = time;
                job.remain = job.run;
                runningQ.push_back(job);
                order.push_back(job.name);
                waitQ.erase(waitQ.begin() + idx);
            } else break;
        }
        for (auto& job : runningQ) {
            if (job.remain > 0) job.remain--;
        }
        time++;
    }
    sort(finishQ.begin(), finishQ.end(), [](const Job& a, const Job& b) {
        return a.name < b.name;
    });
    print_order(order, "短作业优先 SJF");
    print_result(finishQ, "短作业优先 SJF");
}

// 响应比高者优先
void schedule_HRRN(vector<Job> jobs) {
    vector<Job> waitQ = jobs;
    vector<Job> runningQ;
    vector<Job> finishQ;
    vector<string> order;
    int time = 0;

    while (finishQ.size() < jobs.size()) {
        // 检查运行队列，移除已完成作业
        for (auto it = runningQ.begin(); it != runningQ.end();) {
            if (it->remain == 0) {
                Job finished = *it;
                finished.finish = time;
                finished.turnaround = finished.finish - finished.arrive;
                finished.weighted_turnaround = (double)finished.turnaround / finished.run;
                finishQ.push_back(finished);
                it = runningQ.erase(it);
            } else {
                ++it;
            }
        }
        // 运行队列补充（HRRN：从已到达作业中选响应比最高的）
        while (runningQ.size() < 2) {
            int idx = -1;
            double max_response = -1;
            for (int i = 0; i < waitQ.size(); ++i) {
                if (waitQ[i].arrive <= time) {
                    double wait = time - waitQ[i].arrive;
                    double response = (wait + waitQ[i].run) / (double)waitQ[i].run;
                    if (response > max_response) {
                        max_response = response;
                        idx = i;
                    }
                }
            }
            if (idx != -1) {
                Job job = waitQ[idx];
                job.start = time;
                job.remain = job.run;
                runningQ.push_back(job);
                order.push_back(job.name);
                waitQ.erase(waitQ.begin() + idx);
            } else break;
        }
        for (auto& job : runningQ) {
            if (job.remain > 0) job.remain--;
        }
        time++;
    }
    sort(finishQ.begin(), finishQ.end(), [](const Job& a, const Job& b) {
        return a.name < b.name;
    });
    print_order(order, "响应比高者优先 HRRN");
    print_result(finishQ, "响应比高者优先 HRRN");
}

int main() {
    vector<Job> jobs = {
        {"A", 0, 7}, {"B", 2, 10}, {"C", 5, 20}, {"D", 7, 30}, {"E", 12, 40},
        {"F", 15, 8}, {"G", 4, 8}, {"H", 6, 20}, {"I", 8, 10}, {"J", 10, 12}
    };

    schedule_FCFS(jobs);
    schedule_SJF(jobs);
    schedule_HRRN(jobs);

    return 0;
}